﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Net;
using System.Text.RegularExpressions;

namespace ProjectEulerSolutions
{
    /*
     * The rules for writing Roman numerals allow for many ways of writing each number (see About Roman Numerals...). However, there is always a "best" way of writing a particular number.

For example, the following represent all of the legitimate ways of writing the number sixteen:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

The last example being considered the most efficient, as it uses the least number of numerals.

The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; that is, they are arranged in descending units and obey the subtractive pair rule (see About Roman Numerals... for the definitive rules for this problem).

Find the number of characters saved by writing each of these in their minimal form.

Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

     * */
    class Problem89 : IProblem
    {
        enum States
        {
            Begin,
            I,
            Ipv,
            Ipx,
            V,
            Vr,
            X,
            Xr,
            Xpl,
            Xpc,
            L,
            Lr,
            C,
            Cr,
            Cpd,
            Cpm,
            D,
            Dr,
            M,
            Mr,
            E
        }

        public string Calculate()
        {
            WebClient wc = new WebClient();

            String input = wc.DownloadString("http://projecteuler.net/project/roman.txt");

            var numbers = Regex.Matches(input, "[A-Z]+").Cast<Match>().Select(x => x.Value);


            int charsSaved = 0;

            foreach (string s in numbers)
            {
                int n = FromRoman(s);
                string result = ToRoman(n);

                charsSaved += s.Length - result.Length;

                if (s.Length < result.Length)
                {
                    Console.WriteLine("old: {0} -  new: {1} , n: {2}", s, result, n);
                }

            }

            return charsSaved.ToString();
        }

        string ToRoman(int n)
        {
            string result = "";

            while (n >= 1000)
            {
                n -= 1000;
                result += 'M';
            }

            if (n >= 900)
            {
                n -= 900;
                result += "CM";
            }

            if (n >= 500)
            {
                n -= 500;
                result += "D";
            }
            if (n >= 400)
            {
                n -= 400;
                result += "CD";
            }
            while (n >= 100)
            {
                n -= 100;
                result += "C";
            }

            if (n >= 90)
            {
                n -= 90;
                result += "XC";
            }

            if (n >= 50)
            {
                n -= 50;
                result += "L";
            }

            if (n >= 40)
            {
                n -= 40;
                result += "XL";
            }

            while (n >= 10)
            {
                n -= 10;
                result += "X";
            }

            if (n >= 9)
            {
                n -= 9;
                result += "IX";
            }

            if (n >= 5)
            {
                n -= 5;
                result += "V";
            }

            if (n >= 4)
            {
                n -= 4;
                result += "IV";
            }

            while (n >= 1)
            {
                n--;
                result += "I";
            }

            return result;
        }

        int FromRoman(string roman)
        {
            States state = States.Begin;

            int total = 0;

            foreach (char c in roman)
            {
                switch (state)
                {
                    case States.Begin:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                state = States.V;
                                total += 5;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpc;
                                break;
                            case 'L':
                                state = States.L;
                                total += 50;
                                break;
                            case 'C':
                                total += 100;
                                state = States.Cpm;
                                break;
                            case 'D':
                                state = States.D;
                                total += 500;
                                break;
                            case 'M':
                                state = States.M;
                                total += 1000;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.I:
                        if (c != 'I')
                            state = States.E;
                        else
                            total++;
                        break;
                    case States.Ipv:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.I;
                                break;
                            case 'V':
                                total += 4 - 1;
                                state = States.Vr;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Ipx:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.I;
                                break;
                            case 'V':
                                total += 4 - 1;
                                state = States.Vr;
                                break;
                            case 'X':
                                total += 9 - 1;
                                state = States.Xr;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.V:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipv;
                                break;
                            case 'V':
                                total += 5;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Vr:
                        state = States.E;
                        break;
                    case States.X:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Xr:
                        state = States.E;
                        break;
                    case States.Xpl:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.X;
                                break;
                            case 'L':
                                total += 40 - 10;
                                state = States.Lr;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Xpc:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.X;
                                break;
                            case 'L':
                                total += 40 - 10;
                                state = States.Lr;
                                break;
                            case 'C':
                                total += 90 - 10;
                                state = States.Cr;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.L:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpl;
                                break;
                            case 'L':
                                total += 50;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Lr:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.C:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpc;
                                break;
                            case 'L':
                                total += 50;
                                state = States.L;
                                break;
                            case 'C':
                                total += 100;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Cr:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Cpd:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpc;
                                break;
                            case 'L':
                                total += 50;
                                state = States.L;
                                break;
                            case 'C':
                                total += 100;
                                state = States.C;
                                break;
                            case 'D':
                                total += 400 - 100;
                                state = States.Dr;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Cpm:
                        switch (c)
                        {
                            case 'I':
                                total += 1;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpc;
                                break;
                            case 'L':
                                total += 50;
                                state = States.L;
                                break;
                            case 'C':
                                total += 100;
                                state = States.C;
                                break;
                            case 'D':
                                total += 400 - 100;
                                state = States.Dr;
                                break;
                            case 'M':
                                total += 900 - 100;
                                state = States.Mr;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.D:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpc;
                                break;
                            case 'L':
                                total += 50;
                                state = States.L;
                                break;
                            case 'C':
                                total += 100;
                                state = States.Cpd;
                                break;
                            case 'D':
                                total += 500;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Dr:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpc;
                                break;
                            case 'L':
                                total += 50;
                                state = States.L;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.M:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpc;
                                break;
                            case 'L':
                                total += 50;
                                state = States.L;
                                break;
                            case 'C':
                                total += 100;
                                state = States.Cpm;
                                break;
                            case 'D':
                                total += 500;
                                state = States.D;
                                break;
                            case 'M':
                                total += 1000;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.Mr:
                        switch (c)
                        {
                            case 'I':
                                total++;
                                state = States.Ipx;
                                break;
                            case 'V':
                                total += 5;
                                state = States.V;
                                break;
                            case 'X':
                                total += 10;
                                state = States.Xpc;
                                break;
                            case 'L':
                                total += 50;
                                state = States.L;
                                break;
                            default:
                                state = States.E;
                                break;
                        }
                        break;
                    case States.E:
                        return -1;
                }
            }

            return total;
        }
    }
}
